package com.Algorithm.HUAWEI.one20211020;

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2021/10/20/18:48
 * @Description:
 * @Target:
 */
public class 输入长度_字符串_升降_排序 {
    public static void main(String[] args) {

            Scanner input = new Scanner(System.in);
            int len = input.nextInt(); // 长度
            int[] arr = new int[len];


        for (int i = 0; i < len; i++) {
            arr[i]=input.nextInt();
        }


        int flag = input.nextInt(); // 升降
        int l1 = arr.length-1;
        quickProcess(arr,0,l1);


        if (flag==0){
            for (int i : arr) {
                System.out.print(i+" ");
            }
        }else {
            while (l1>=0){
                System.out.print(arr[l1--]+" ");
            }
        }





        }














// --------------------------------------------------------------------------------------------
    // 快排
    // 快排在二分的基础上,加入一个随机动的数




    public static void quickProcess(int[] arr,int L,int R){
        if(L<R){
            // 先交换末尾的随机
            swap(arr,(L+(int)(Math.random()*(R-L+1))),R);


            int[] part = part(arr, L, R);

            quickProcess(arr,L,part[0]-1);
            quickProcess(arr,part[1]+1,R);

        }


    }



    // 数组内[L,R-1]
    // 荷兰国旗,双指针,左右跑,数组正常跑
    public static int[] part(int[] arr,int L,int R){
        int i = L;  // 数组
        int left = L-1; // 左边界
        int right = R; // 右边界

        while (i<right){
            if(arr[i]<arr[R]){
                swap(arr,++left,i++);
            }else if(arr[i]>arr[R]){
                swap(arr,--right,i);
            }else {
                i++;
            }
        }

        swap(arr,right,R);
        return new int[]{left+1,right};
    }








    // 交换
    public static void swap(int[] arr, int i , int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


// --------------------------------------------------------------------------------------------


}
